Transactions on Combinatorics
Volume:11 Issue: 3, Sep 2022

We describe the Italy-South Africa Research Program 2018--2020, focusing on the mobility scheme ``Algebraic Graph Theory and Complex Networks'' which supported a series of scientific initiatives between the University of Cape Town (Cape Town, South Africa) and the University of Naples Federico II (Naples, Italy) during the years 2018--2021. We sketch the relevant steps of the collaboration, focusing on the creation of a network of researchers between Italy and South Africa in the fields of Graph Theory and Combinatorics. In this context it becomes more relevant the role of the ``Workshop on Graphs, Topology and Topological Groups 2021'' and of the corresponding proceedings.

It has been recently observed that a topological decomposition of the Pauli group, as central product of the quaternion group of order eight and the cyclic group of order four, influences some significant dynamical systems in mathematical physics. The connection between groups of symmetries and dynamical systems is in fact well known, but looking specifically at the algebraic and topological decompositions of the Pauli group, we find conditions for the existence of a Riemannian 3-manifold whose fundamental group is epimorphically mapped onto a central product.

Let T be the multiplicative group of complex units, and let L(Φ) denote the Laplacian matrix of a nonempty T-gain graph Φ=(Γ,T,γ). The gain line graph L(Φ) and the gain subdivision graph S(Φ) are defined up to switching equivalence. We discuss how the eigenspaces determined by the adjacency eigenvalues of L(Φ) and S(Φ) are related with those of L(Φ).

The Basilica group is one of the most studied automaton groups, and many papers have been devoted to the investigation of the characteristic polynomial and spectrum of the associated Schreier graphs {Γn}n≥1, even if an explicit description of them has not been given yet. Our approach to this issue is original, and it is based on the use of the Coefficient Theorem for signed graphs. We introduce a signed version Γ−n of the Basilica Schreier graph Γn, and we prove that there exist two fundamental relations between the characteristic polynomials of the signed and unsigned versions. The first relation comes from the cover theory of signed graphs. The second relation is obtained by providing a suitable decomposition of Γn into three parts, using the self-similarity of Γn, via a detailed investigation of its basic figures. By gluing together these relations, we find out a new recursive equation which expresses the characteristic polynomial of Γn as a function of the characteristic polynomials of the three previous levels. We are also able to give an explicit description of the eigenspace associated with the eigenvalue 2, and to determine how the eigenvalues are distributed with respect to such eigenvalue.

This survey is intended to be a fast (and reasonably updated) reference for the theory of Stallings automata and its applications to the study of subgroups of the free group, with the main accent on algorithmic aspects. Consequently, results concerning finitely generated subgroups have greater prominence in the paper. However, when possible, we try to state the results with more generality, including the usually overlooked non-(finitely-generated) case.

Given a T0-quasi-metric space we associate a directed graph with it and study some properties of the related directed graph. The present work complements and refines earlier work in the field in which the symmetry graph of a T0-quasi-metric space was studied.

We investigate a trivariate polynomial associated with rooted trees. It generalises a bivariate polynomial for rooted trees that was recently introduced by Liu. We show that this polynomial satisfies a deletion-contraction recursion and can be expressed as a sum over maximal antichains. Several combinatorial quantities can be obtained as special values, in particular the number of antichains, maximal antichains and cutsets. We prove that two of the three possible bivariate specialisations characterise trees uniquely up to isomorphism. One of these has already been established by Liu, the other is new. For the third specialisation, we construct non-isomorphic trees with the same associated polynomial. We finally find that our polynomial can be generalised in a natural way to a family of posets that we call Ѵ-posets. These posets are obtained recursively by either disjoint unions or adding a greatest/least element to existing Ѵ-posets.

Given a finite group G and the subgroups lattice L(G) of G, the \textit{non--permutability graph of subgroups} ΓL(G) is introduced as the graph with vertices in L(G)∖CL(G)(L(G)), where CL(G)(L(G)) is the smallest sublattice of L(G) containing all permutable subgroups of G, and edges obtained by joining two vertices X,Y if XY≠YX. Here we study the behaviour of the non-permutability graph of subgroups using algebraic properties of associated matrices such as the adjacency and the Laplacian matrix. Further, we study the structure of some classes of groups whose non-permutability graph is strongly regular.